//![image.png](https://pic.leetcode.cn/1682649184-tSKGBe-image.png)

#include <cstdlib>
#include <unordered_map>
#include <vector>
using namespace std;
class RandomizedSet
{
private:
    // 哈希表为倒排索引
    //[val,index]
    unordered_map<int, int> umap;
    // 数组为正排索引 存储数据
    //[index,val]
    vector<int> vt;

public:
    /** Initialize your data structure here. */
    RandomizedSet()
    {
        // 本题不追求随机度 节省时间
        // srand((unsigned int)time(nullptr));
    }
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val)
    {
        if (umap.find(val) != umap.end())
            return false;
        vt.push_back(val);
        umap[val] = vt.size() - 1;
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val)
    {
        auto it = umap.find(val);
        if (it == umap.end())
            return false;
        // 与最后一个元素交换实现删除:交换数据(O(1))+调整最后元素映射(O(1))+popback(O(1))+erase(O(1))
        if (it->first != vt.back())
        {
            vt[it->second] = vt.back();
            umap[vt.back()] = it->second;
        }
        umap.erase(it);
        vt.pop_back();
        return true;
    }

    /** Get a random element from the set. */
    int getRandom()
    {
        return vt[rand() % vt.size()];
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */